HW#2 --- last modified February 07 2019 23:05:41..

Solution set.

Due date: Oct 10

Files to be submitted:
  Hw2.zip

Purpose:

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO2 -- Understand the implementation of modern symmetric ciphers such as RC4, DES and TEA; understand public key cryptosystems such as RSA, Diffie-Hellman and the knapsack; understand the implementation of a hash function, such as Tiger.

Specification:

This homework consists of two parts: A set of book problems, which are to be done individually, should be handwritten (no typing), and must be turned in at the start of class on the day indicated; a coding assignment, which can be done in a team of at most three people. For the coding portion only one team member needs to submit -- just be sure to mention the names of your teammates in the documentation for your code.

The book problems I want you to do are: Ch 4, Exercise 5 and 6 (due Sep. 19); Ch 5, Exercise 4 and 5 (due Oct. 3). One problem each week will be graded and it will be worth up to 1pt. The score given will be one the following: 0 (incorrect answer or insufficient justification), 0.5 (incorrect answer but some reasonable justification; or correct answer but justification only partly correct), 1 (correct answer and well-reasoned and correct justification).

For the coding part of this homework I would like you to write two Java programs: Rc4.java and KnapsackCrypto.java. These two files should be contained in the Hw2.zip file you submit -- do not include class files or project files or any other files. Your code will be compiled from the command line with the lines:

javac Rc4.java
javac KnapsackCrypto.java

You can assume the grader has a Java 1.6 compiler. The first program will be run from the command-line with a line of the following format:

java Rc4 key_file.txt plain_cipher.txt action

Here key_file.txt contains a string of up to 256 bytes (might be less) representing an RC4 key; plain_cipher.txt is a file containing UTF-8 plaintext or containing the results of encrypting some plaintext using RC4, action is either encrypt or decrypt. If the action is encrypt your program should try to encrypt plain_cipher.txt using your implementation of RC4 and the key in key_file.txt. The version of RC4 you use should be the version described in class which discards the first 256 bytes of keystream. If the action is decrypt, then your program should try to decrypt plain_cipher.txt using the key in keystream.txt. Output of encrypt/decrypt actions should be to standard out (use System.out).

KnapsackCrypto.java should contain your implementation of the Merkle Hellman crypto system as described in class. It will be run from the command-line in one of two ways:

java KnapsackCrypto key_file.txt
or
java KnapsackCrypto key_file.txt plain_cipher.txt

In the first way, the file key_file.txt is expected to contain three lines: the first line contains an integer representing a modulus, the second line is a multiplicative inverse, and the third line contains a superincreasing positive integer sequence (no whitespace). For example,

491
12
2,3,7,14,30,57,120,251

Using these numbers, KnapsackCrypto should compute the multiplicative inverse of the conversion factor using the extended Euclidean algorithm, output it to standard out, and then on the line below use this number to output a comma separated general knapsack. So for the example above, the output would be:

41
82,123,287,83,248,373,10,471

For the second way KnapsackCrypto can be run, your program should first determine if key_file.txt contains one or three lines. If it has neither, then it should output to standard out "Bad Key File!". If it has one line, it should check that it consists of comma separated positive integers, and if so, use them as a knapsack public key to encrypt plain_cipher.txt. Similarly, if it has three lines, your program should check if they contain a knapsack private key using the encoding given in the first way above. If so, it should try to use this private key to decrypt plain_cipher.txt. If the message is longer then the block length, that comes from the key, cipher block chaining should be used to continue encrypting. To keep things simple you can skip the initialization vector (or assume it is 0).